﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 算法基本功.算法._0_数组._1_双指针.快慢指针
{
    /// <summary>
    /// 这道题的关键是理解原地删除重复元素的意义 然后就无非是多一些判断条件
    /// </summary>
    internal class 删除有序数组中的重复项_II
    {
        // 删除出现两次以上的元素说是 这种有序的数组 几乎首先都想到快慢指针遍历一遍即可
        public int RemoveDuplicates(int[] nums)
        {

            int slow = 0, fast = 0, count = 0; //count额外记录重复元素的个数

            while (fast < nums.Length)
            {
                //如果元素不重复 则slow指针后移 并将元素复制到slow指针指向的位置以保证原地修改
                if (nums[fast] != nums[slow])
                {
                    slow++;
                    nums[slow] = nums[fast];
                }
                //允许出现一次重复 因此count的条件比较重要 同时也避免一下自己复制自己
                else if (nums[fast] == nums[slow] && slow < fast && count < 2)
                {
                    slow++;
                    nums[slow] = nums[fast];
                }

                //上述条件都不满足 说明出现了重复的元素 因此count和fast都要后移
                count++;
                fast++;

                //如果遇到了新的元素 并且没有越界 则重置其count
                if (fast < nums.Length && nums[fast] != nums[fast - 1])
                {
                    count = 0;
                }

            }
            //最终slow指向了新数组的最后一个index 因此需要+1来返回数组长度
            return slow + 1;

        }

        //但是还有更简洁的写法 利用数组有序的特点 
        //如果slow == slow + 2说明此子断不可留
        //因此反过来看 slow != slow + 2 则说明此子可留 默认就满足条件
        //因此让fast代替slow + 2的位置即可
        public int RemoveDuplicatesMaster(int[] nums)
        {
            if (nums.Length <= 2) return nums.Length;
            int slow = 2;

            for (int fast = 2; fast < nums.Length; fast++)
            {
                if (nums[fast] != nums[slow - 2])
                {
                    //维护新数组
                    nums[slow] = nums[fast];
                    slow++;
                }
            }

            return slow;
        }
    }
}
